package com.LeeCode;

/**
 * 丑数 III
 */

public class Code1201 {
    public static void main(String[] args) {
        System.out.println(new Code1201().nthUglyNumber(3, 2, 3, 5));
    }

    public int nthUglyNumber(int n, int a, int b, int c) {
        long lcm1 = lcm(a, b), lcm2 = lcm(a, c), lcm3 = lcm(b, c), lcm4 = lcm(lcm1, c);

        long left = Math.min(a, Math.min(b, c)) + n - 2;
        long right = (long) Math.min(a, Math.min(b, c)) * n;

        while (left + 1 < right) {
            long mid = left + (right - left) / 2;
            // 根据容斥原理计数
            long count = mid / a + mid / b + mid / c
                    - mid / lcm1 - mid / lcm2 - mid / lcm3
                    + mid / lcm4;
            if (count >= n)
                right = mid;
            else
                left = mid;
        }

        return (int) right;
    }

    private long gcd(long a, long b) {
        while (a != 0) {
            long temp = a;
            a = b % a;
            b = temp;
        }
        return b;
    }

    private long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }
}
